int max(int a, int b) {
    return a>b ?a: b;
}


int maxPro2(int ps[], int psS) {
    
    int maxpro = 0;
    int i=1;
    for(i=1; i<psS; i++)
        if(ps[i]>ps[i-1])
            maxpro += ps[i]-ps[i-1];
    
    return maxpro;
    
}

#define MININT (1<<(8*sizeof(int)-1))

int maxProfit(int k, int* prices, int psS) {
    if(k >= psS/2) return maxPro2(prices, psS);
    typedef int SubA[k+1];
    SubA *dp = calloc(psS+1, sizeof(SubA));
    //dp[i][x], 0<i<psS, 0<x<=k:在0---i-1天内最多进行x次交易所能获得的最大收益,不要求一定要交易够x次，不超过即可
    //dp[i][x] = max(dp[i-1][x], {dp[j][x-1]+prices[i]-prices[j]|0<j<i})
    //1)dp[i-1][x] :如果最大收益不用在第i-1天交易(卖出)
    //2)dp[j][x-1]+prices[i]-prices[j] :如果最大收益需要在第i-1天交易---最后一次在第j天买入，在第i-1天卖出
    
    int x;
    for(x=0; x<=k; x++)
        dp[0][x] = dp[1][x] = 0;
    int i;
    int j;
    //int *maxpre1 = calloc(psS, sizeof(int));
    //int *maxpre2 = calloc(psS, sizeof(int));
    for(x=1; x<=k; x++) {
        for(i=2; i<=psS; i++) {
            dp[i][x] = dp[i-1][x];
            #if 1
            for(j=0; j<i-1; j++)
                dp[i][x] = max(dp[i][x], dp[j][x-1]+prices[i-1]-prices[j]);
            #endif
        }
        
    }
    return dp[psS][k];
    
}
